Calcul d'un PGCD - Pour aller plus loin - Corrigé

Énoncé

Soit \(a \in \mathbb{N}^\ast\) et \(b \in \mathbb{Z}\) . Déterminer \(\mathrm{PGCD}(ab;b(3a+1))\) .

Solution

On a \(\begin{align*}\mathrm{PGCD}(ab;b(3a+1))=\left\vert b \right\vert \times \mathrm{PGCD}(a;3a+1)\end{align*}\) par homogénéité du PGCD.

Il reste donc à calculer \(\mathrm{PGCD}(a;3a+1)\) .

• La division euclidienne de \(3a+1\) par \(a\) s'écrit :
  \(3a+1=a \times 3+1\) lorsque \(0 \leqslant 1 c'est-à-dire lorsque \(a \neq 1\) .
  En utilisant l'algorithme d'Euclide, on a ensuite \(a = 1 \times a+0\) , et donc \(\mathrm{PGCD}(a;3a+1)=1\) .
• Lorsque \(a=1\) , on a \(\mathrm{PGCD}(a;3a+1)=\mathrm{PGCD}(1;4)=1\) .

On en déduit que \(\mathrm{PGCD}(a;3a+1)=1\) , et donc que \(\mathrm{PGCD}(ab;b(3a+1))=\left\vert b \right\vert \times 1=\left\vert b \right\vert\) .

Remarque

Le théorème de Bézout (voir la suite du cours) permet de généraliser facilement cet exercice lorsque  \(a\)  est un entier relatif quelconque (et non seulement pour \(a \in \mathbb{N}^\ast\) ). 
En effet, l'égalité \(1 \times (3a+1)-3 \times a=1\) permet d'affirmer (grâce au théorème de Bézout) que \(\mathrm{PGCD}(a;3a+1)=1\) pour tout \(a \in \mathbb{Z}\) .